package com.leetcode.LeetCode精选TOP面试题;


/**
 * @author 覃国强
 * @date 2022-06-29 18:01
 */
public class 题库_0146_LRU缓存 {

  public static void main(String[] args) {
    LRUCache lruCache = new LRUCache(2);
    lruCache.put(2, 1);
    lruCache.printCache();
    lruCache.put(1, 1);
    lruCache.printCache();
    lruCache.put(2, 3);
    lruCache.printCache();
    lruCache.put(4, 1);
    lruCache.printCache();
    System.out.println(lruCache.get(1));
    lruCache.printCache();
    System.out.println(lruCache.get(2));
    lruCache.printCache();
  }


  static
  class LRUCache {

    private final Node[] nodes;

    private int size;

    /**
     * 头节点表示最久被访问的数据
     */
    private final Node head;

    /**
     * 尾结点表示最近被访问的数据
     */
    private Node tail;

    public LRUCache(int capacity) {
      nodes = new Node[capacity];
      size = 0;
      head = new Node();
      tail = head;
    }

    public int get(int key) {
      Node node = internalGet(key);
      return node == null ? -1 : node.value;
    }

    private Node internalGet(int key) {
      int index = key % nodes.length;
      Node node = nodes[index];
      while (node != null && node.key != key) {
        node = node.next;
      }
      if (node == null) {
        return null;
      }

      // 将当前节点移动到尾部
      moveToListTail(node);

      return node;
    }

    private void insertToHash(Node node) {
      int index = node.key % nodes.length;
      if (nodes[index] == null) {
        nodes[index] = node;
      } else {
        Node prev = nodes[index];
        while (prev.next != null) {
          prev = prev.next;
        }
        prev.next = node;
      }
    }

    private void removeFromHash(Node delete) {
      int index = delete.key % nodes.length;
      if (nodes[index].key == delete.key) {
        nodes[index] = delete.next;
      } else {
        Node prev = nodes[index];
        while (prev.next.key != delete.key) {
          prev = prev.next;
        }
        prev.next = delete.next;
      }
      delete.next = null;
    }

    private void insertToListTail(Node node) {
      tail.suffix = node;
      node.prefix = tail;
      tail = node;
    }

    private Node removeListHead() {
      Node delete = head.suffix;
      head.suffix = delete.suffix;
      head.suffix.prefix = head;
      delete.suffix = null;
      delete.prefix = null;
      return delete;
    }

    private void reduce() {
      if (size > nodes.length) {
        Node delete = removeListHead();
        removeFromHash(delete);
        --size;
      }
    }

    public void put(int key, int value) {
      // 先 get 一次，如果存在，node 则已经被移动到尾部了
      Node node = internalGet(key);
      if (node == null) {
        node = new Node(key, value);
        insertToHash(node);

        // 插入链表尾部
        insertToListTail(node);
        ++size;

        reduce();
      } else {
        node.value = value;
      }
    }

    public void printCache() {
      Node node = head.suffix;
      while (node != null) {
        System.out.print("(" + node.key + "," + node.value + "), ");
        node = node.suffix;
      }
      System.out.println();
    }

    private void moveToListTail(Node node) {
      if (tail != node) {
        Node prev = node.prefix;
        Node last = node.suffix;

        prev.suffix = last;
        last.prefix = prev;

        tail.suffix = node;
        node.prefix = tail;
        node.suffix = null;
        tail = node;
      }
    }

    static class Node {
      int key;
      int value;
      Node next;
      Node prefix;
      Node suffix;

      Node(){}

      Node(int key, int value) {
        this.key = key;
        this.value = value;
      }

    }

  }

}
